An interconnection network consists of a set of nodes connected by channels. Such networks are used to transport data packets between nodes. They are used, for example, in multicomputers, multiprocessors, and network switches and routers. In multicomputers, they carry messages between processing nodes. In multiprocessors, they carry memory requests from processing nodes to memory nodes and responses in the reverse direction. In network switches and routers, they carry packets from input line cards to output line cards. For example, pending U.S. patent application Ser. No. 08/918,556, filed by William J. Dally, Philip P. Carvey, Larry R. Dennison and P. Alan King for Internet Switch Router, describes the use of a three-dimensional torus interconnection network to provide the switching fabric for an internet router.
The arrangement of the nodes and channels in a network defines its topology. FIG. 1, for example, illustrates a two-dimensional, radix-8 torus topology, also called an 8-ary 2-cube. In this topology each node is designated by a two-digit radix-8 address. Channels in both directions connect each pair of nodes whose addresses differ by one in exactly one digit modulo 8. That is, node (a,b) is connected to nodes (a−1,b),(a+1,b),(a,b−1), and (a,b+1) where the addition and subtraction are performed modulo-8. Each node in this topology has degree 4 since it is connected to four other nodes. A related topology, an 8-ary 2-mesh, is shown in FIG. 2. This network is identical to the 8-ary 2-cube except that the ‘end-around’ connections from node 7 to node 0 in each dimension are omitted. While the mesh network is simpler to wire, it has significantly lower performance than the torus network as will be described below.
Meshes and tori may be constructed with different radices and numbers of dimensions, and other network topologies are possible such as crossbars, trees, and butterfly networks. Several popular topologies are described, for example, by William J. Dally, “Network and Processor Architectures for Message-Driven Computers,” in VLSI and Parallel Computation, Edited by Suaya and Birtwistle, Morgan Kaufmann, 1990.
The topology chosen for an interconnection network is constrained by the technology used to implement the network. Pin-count constraints on chips, circuit boards, and backplanes, for example, limit the maximum degree of each network node. Wire-length constraints limit the maximum distance a single channel can traverse when the network is mapped into a physical packaging structure.
Low-dimensional (2–3 dimensions) torus and mesh networks have become popular in recent years in part because they offer good performance while having a small node degree and uniformly short wires when mapped to two or three dimensional electronic packaging systems. While at first it may appear that the end-around channels in a torus network result in long wires, these long wires can be avoided by folding the torus as illustrated in FIG. 3. The figure shows how an 8×4 torus that is folded in the x-dimension is mapped onto a set of backplanes 20. Each node is packaged on a circuit card and eight of these circuit cards are inserted in each backplane 20. The circuit cards in each backplane span two x coordinates and the entire y dimension. The y-dimension channels are realized entirely in the backplane while the x-dimension channels are realized by connections between backplanes. Folding the torus allows this topology to be realized with each x-channel connecting no further than the adjacent backplane.
To expand the network of FIG. 3, it is necessary to first break the loop-back connection 22 or 24 at the end of the x-dimension and then make a connection to a new backplane. An efficient method for reconfiguring the network in this manner is disclosed in pending U.S. patent application Ser. No. 09/083,722, filed by Philip P. Carvey, William J. Dally and Larry R. Dennison for Apparatus and Methods for Connecting Modules Using Remote Switching.
Two important measures of the quality of a topology are average path length and maximum channel load. The average path length, Davg, of a network is the average number of channels that must be traversed to send a packet between two randomly selected nodes in a network. In the radix-8, two-dimensional torus network of FIG. 1, the average packet traverses two channels in each dimension, giving Pavg=4. In general, the average path length in a k-ary n-cube is kn/4 (for k even) and n(k/4−1/4k) (for k odd) while the average path length in a k-ary n-mesh is n(k/3−1/3k). Average path length is a good predictor of network latency. The lower the average path length of a topology, the lower is the latency of a network using that topology, assuming the latency of an individual channel remains constant.
The maximum channel load of a network, Cmax, is the largest number of packets that traverse a single channel when all nodes send packets to all other nodes divided by the number of nodes squared. In the 8-ary 2-cube network of FIG. 1, for example, the channel load is uniform with Cmax=Ci=1 for every channel i. In general, the maximum channel load in a k-ary n-cube is k/8 while the maximum channel load in a k-ary n-mesh is k/4. Maximum channel load is a good predictor of the throughput of a network. The lower the maximum channel load of a topology, the higher is the throughput of a network using that topology, assuming the bandwidth of an individual channel remains constant.